#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define MIN_NUM -2147483648

typedef struct MinHeap {
	int* Data;
	int Size;
	int Capacity;
};

typedef struct HuffmanNode
{
	int weight;
	struct HuffmanNode* left;
	struct HuffmanNode* right;
};

MinHeap* creatHeap(int size)
{
	MinHeap* heap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
	int* nums = (int*)malloc(sizeof(int) * 10);
	if (heap != NULL && nums != NULL)
	{
		heap->Data = nums;
		heap->Size = 0;
		heap->Capacity = size;
		for (int i = 0; i < 10; i++)
		{
			(heap->Data)[i] = 0;
		}
		//Data[0] is not a part of heap!
		heap->Data[0] = MIN_NUM;
	}
	return heap;
}

int insertHeap(MinHeap* heap, int ele)
{ 
	//Data[0] is a guard
	int i;
	if (heap->Size == heap->Capacity)
	{
		std::cout << "Heap is full." << std::endl;
		return 0;
	}
	//If element smaller than father, exchange their sit
	for (i = heap->Size + 1; ele < heap->Data[i / 2]; i /= 2)
	{
		heap->Data[i] = heap->Data[i / 2];
	}
	heap->Data[i] = ele;
	heap->Size++;
	return 1;
}

int deleteMin(MinHeap* heap)
{
	int parent;
	int child;
	int minItem;
	int x;

	if (heap->Size == 0)
	{
		std::cout << "Heap is empty." << std::endl;
		return MIN_NUM;
	}
	//Data[1] is minimum number in this heap
	minItem = heap->Data[1];
	//Last element exchange with root element
	x = heap->Data[heap->Size];
	heap->Size--;
	//Judge whether parent have a child
	for (parent = 1; parent*2 <= heap->Size; parent = child)
	{
		//Child equals 2 times the parent sign
		child = parent * 2;
		//Find a smaller child
		if ((child != heap->Size-1) && 
			(heap->Data[child] > heap->Data[child+1]))
		{
			child++;
		}
		if (x <= heap->Data[child])  
		{
			//Have fund a right position
			break;
		}
		else
		{
			//Parent exchange with child
			heap->Data[parent] = heap->Data[child];
		}
	}
	heap->Data[parent] = x;
	return minItem;
}


HuffmanNode* buildHuffman(MinHeap* heap)
{
	HuffmanNode* hNode = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));
	//Merge tow minimum heap element
	for (int i = 1; i < heap->Size - 1; i++)
	{
		HuffmanNode* hNodeLeft  = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));
		HuffmanNode* hNodeRight = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));
		if (hNodeLeft  != NULL &&
			hNodeRight != NULL &&
			hNode      != NULL)
		{
			hNodeLeft->weight = deleteMin(heap);
			hNodeRight->weight = deleteMin(heap);

			hNode->left = hNodeLeft;
			hNode->right = hNodeRight;

			hNode->weight = hNode->left->weight + hNode->right->weight;

			insertHeap(heap, hNode->weight);
			//Do not Finish
		}

	}
	return hNode;
}


int main(void)
{
	int nums[10] = { 85,22,90,86,80,54,3,11,18,4 };
	MinHeap* heap = creatHeap(10);

	for (int i = 0; i < 10; i++)
	{
		int status = insertHeap(heap, nums[i]);
		if (!status)
		{
			std::cout << "Insert Erro!" << std::endl;
			break;
		}
	}
	HuffmanNode* hNode = buildHuffman(heap);

	std::cout << "Done" << std::endl;
}